package 简单.投票算法;

/**
 * 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。若没
 * 有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
 * <p>
 * 注意：Boyer-Moore 投票算法只能找到出现次数超过一半或者等于一半的元素
 */
public class 主要元素_17_10 {

    public static void main(String[] args) {
        int[] nums = {3, 2, 3, 5};
        int i = majorityElement(nums);
        System.out.println(i);

    }

    //Boyer-Moore 投票算法
    public static int majorityElement(int[] nums) {
        //消消乐
        int candidate = nums[0], count = 0;
//        int appear = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        //初始化count，无需再次创建一个对象浪费内存
        count = 0;
        //校验candidate出现次数是否超过一半
        for (int num : nums) {
            if (candidate == num) {
                count++;
            }
        }
        return count > nums.length / 2 ? candidate : -1;
    }

}
